﻿/*************************************自己敲的第一个版本*******************************************************/
//#pragma once
//#include <iostream>
//#include <assert.h>
//using namespace std;
//
//// 枚举值表示颜色
//enum Color
//{
//	RED,
//	BLACK
//};
//
//// 这里默认按 key/value 结构实现
//template <class K, class V>
//struct RBTreeNode {
//	// 这里更新控制平衡也要加入 parent指针
//	pair<K, V> _kv;
//	RBTreeNode<K, V>* _left;
//	RBTreeNode<K, V>* _right;
//	RBTreeNode<K, V>* _parent;
//	Color _color;
//
//	RBTreeNode (const pair<K, V>& kv)
//		:_kv(kv)
//		,_left(nullptr)
//		,_right(nullptr)
//		,_parent(nullptr)
//		,_color(RED)
//	{ }
//};
//
//
//template<class K, class V>
//class RBTree {
//	typedef RBTreeNode<K, V> Node;
//public:
//	bool Insert(const pair<K, V>& kv) {
//		if (_root == nullptr) {
//			_root = new Node(kv);
//			_root->_color = BLACK;
//			return true;
//		}
//
//		Node* parent = nullptr;
//		Node* cur = _root;
//		while (cur) {
//			if (cur->_kv.first < kv.first) {
//				parent = cur;
//				cur = cur->_right;
//			}
//			else if (cur->_kv.first > kv.first) {
//				parent = cur;
//				cur = cur->_left;
//			}
//			else {
//				// 遇到相同键的值
//				return false;
//			}
//		}
//		// 退出while循环后，cur为空指针
//		cur = new Node(kv);
//		// 判断 cur 是在 parent 的左边还是右边
//		if (kv.first < parent->_kv.first) {
//			parent->_left = cur;
//			cur->_parent = parent;
//		}
//		else {
//			parent->_right = cur;
//			cur->_parent = parent;
//		}
//
//		// 目前新结点是染的红色，现在向上判断是否需要 对结点重新染色
//		while (parent) {
//			// 如果父结点是 黑色，则不需要继续往上调整了
//			if (parent->_color == BLACK) {
//				// 默认 根结点为 黑色
//				_root->_color = BLACK;
//				return true;
//			}
//			else if (parent->_color == RED) {
//				Node* grandfather = parent->_parent;
//				Node* uncle = nullptr;
//				if (parent == grandfather->_left) {
//					uncle = grandfather->_right;
//				}
//				else {
//					uncle = grandfather->_left;
//				}
//				// uncle 结点可能为空结点
//				if (uncle != nullptr && uncle->_color == RED) {
//					grandfather->_color = RED;
//					uncle->_color = parent->_color = BLACK;
//					// 继续向上传递
//					cur = grandfather;
//					parent = cur->_parent;
//				}
//				else if ((uncle == nullptr) || (uncle != nullptr && uncle->_color == BLACK)) {
//					// uncle 结点是空结点 或者 uncle 结点的颜色为 黑色
//					// 采用 旋转+调色，根据情况采用四种旋转方式后
//					// 对 grandfather、parent 结点调色
//					// LL
//					if (grandfather->_left == parent && parent->_left == cur) {
//						RotateR(grandfather);
//						parent->_color = BLACK;
//						grandfather->_color = cur->_color = RED;
//					}
//					// LR
//					else if (grandfather->_left == parent && parent->_right == cur) {
//						RotateLR(grandfather);
//						cur->_color = BLACK;
//						grandfather->_color = parent->_color = RED;
//					}
//					// RR
//					else if (grandfather->_right == parent && parent->_right == cur) {
//						RotateL(grandfather);
//						parent->_color = BLACK;
//						grandfather->_color = cur->_color = RED;
//					}
//					// RL
//					else if (grandfather->_right == parent && parent->_left == cur) {
//						RotateRL(grandfather);
//						cur->_color = BLACK;
//						grandfather->_color = parent->_color = RED;
//					}
//					else {
//						// 出现异常情况，不符合四种旋转情况
//						assert(false);
//					}
//
//				}
//				else {
//					// uncle 结点发生异常情况，uncle结点既不为空，也不是 红黑染色
//					assert(false);
//				}
//			}
//			else {
//				// 发生了异常情况，结点的颜色 非黑非红
//				assert(false);
//			}
//		}
//
//		// 默认 根结点为 黑色
//		_root->_color = BLACK;
//		return true;
//	}
//
//	void InOrder() {
//		_InOrder(_root);
//		cout << endl;
//	}
//
//	bool Check(Node* root, int blackNum, const int refNum) {
//		if (root == nullptr) {
//			// 前序遍历走到空时，意味着一条路径走完了
//			// cout << blackNum << endl;
//			if (refNum != blackNum) {
//				cout << "存在黑色结点的数量不相等的路径" << endl;
//				return false;
//			}
//			return true;
//		}
//
//		// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了
//		if (root->_color == RED && root->_parent && root->_parent->_color == RED) {
//			// 违反了 不红红规则
//			cout << root->_kv.first << "存在连续的红色结点" << endl;
//			return false;
//		}
//
//		if (root->_color == BLACK) {
//			blackNum++;
//		}
//
//		return Check(root->_left, blackNum, refNum)
//			&& Check(root->_right, blackNum, refNum);
//	}
//
//	bool IsBalanceTree() {
//		if (_root == nullptr) {
//			cout << "根结点为空，这是一棵空树" << endl;
//			return false;
//		}
//
//		if (_root->_color == RED) {
//			cout << "根结点为红色" << endl;
//			return false;
//		}
//
//		// 参考值
//		int refNum = 0;
//		Node* cur = _root;
//		while (cur) {
//			if (cur->_color == BLACK) {
//				++refNum;
//			}
//			cur = cur->_left;
//		}
//
//		return Check(_root, 0, refNum);
//	}
//private:
//	void RotateL(Node* cur) {	// 左单旋
//		Node* parent = cur->_parent;
//		Node* subR = cur->_right;
//		Node* subRL = subR->_left;
//
//		// 先操作 subR 和 subRL 之间的链接
//		// 左单旋的目的，是让 subR 替代 cur 作为子树的根结点
//		subR->_left = cur;
//		cur->_parent = subR;
//		cur->_right = subRL;	// sub 的左子树归 cur 的右孩子指针管
//
//		// subRL 可以为空， 就是高度 h 为 0 的时候
//		// 所以需要特判
//		if (subRL != nullptr)
//			subRL->_parent = cur;
//
//		// 注意 cur 的父结点 parent 还链接着 cur，需要断开链接，让 parent的其中一个孩子指针指向 subR
//		// 同时 parent 作为 cur 的父结点，当 cur 为根结点时，parent 为空，也需要特判
//		if (parent == nullptr) {
//			// 说明 cur 是根结点
//			_root = subR;
//			subR->_parent = nullptr;
//		}
//		else {
//			// 说明 cur 不是根节点
//			if (cur == parent->_left) {
//				parent->_left = subR;
//			}
//			else {
//				parent->_right = subR;
//			}
//			subR->_parent = parent;
//		}
//	}
//
//	void RotateR(Node* cur) {	// 右单旋
//		Node* parent = cur->_parent;// cur的父结点
//		Node* subL = cur->_left;	// cur的左孩子
//		Node* subLR = subL->_right;	// subL的右孩子
//
//		// cur 成为 subL 的右孩子
//		subL->_right = cur;
//		cur->_parent = subL;
//
//		// subLR 成为 cur 的左孩子
//		cur->_left = subLR;
//		if (subLR != nullptr)
//			subLR->_parent = cur;
//
//		if (parent == nullptr) {
//			// 说明 cur 是根结点，parent 才为空结点
//			_root = subL;
//			subL->_parent = nullptr;
//		}
//		else {
//			// parent 是非空结点， 但是不知道 cur 是 parent 的哪个孩子
//			if (cur == parent->_left) {
//				parent->_left = subL;
//			}
//			else {
//				parent->_right = subL;
//			}
//			subL->_parent = parent;
//		}
//	}
//
//	void RotateLR(Node* cur) {	// 左右双旋
//		Node* subL = cur->_left;
//		Node* subLR = subL->_right;
//
//		RotateL(subL);
//		RotateR(cur);
//
//	}
//
//	void RotateRL(Node* cur) {
//		Node* subR = cur->_right;
//		Node* subRL = subR->_left;
//
//		RotateR(subR);
//		RotateL(cur);
//
//	}
//
//	void _InOrder(Node* root) {
//		if (root == nullptr) {
//			return;
//		}
//
//		_InOrder(root->_left);
//		cout << root->_kv.first << " ";
//		_InOrder(root->_right);
//	}
//private:
//	Node* _root = nullptr;
//};




/**************************************根据板书敲的第二个代码****************************************************/
//// 枚举值表示颜色
//enum Colour {
//	RED,
//	BLACK
//};
//
//// 实现通用的 结点
//template<class T>
//struct RBTreeNode {
//	T _data;
//	RBTreeNode<T>* _left;
//	RBTreeNode<T>* _right;
//	RBTreeNode<T>* _parent;
//	Colour _color;
//
//	RBTreeNode(const T& data)
//		:_data(data)
//		,_left (nullptr)
//		,_right(nullptr)
//		,_parent(nullptr)
//		,_color(Colour::RED)
//	{ }
//};
//
//template<class K, class T>
//class RBTree {
//	typedef RBTreeNode<T> Node;
//public:
//	bool Insert(const T& data) {
//		if (_root == nullptr) {
//			_root = new Node(data);
//			_root->_color = Colour::BLACK;
//			return true;
//		}
//
//		Node* parent = nullptr;
//		Node* cur = _root;
//
//		KeyOfT kot;
//		while (cur) {
//			if (kot(cur->_data) < kot(data)) {
//				parent = cur;
//				cur = cur->_right;
//			}
//			else if (kot(cur->_data) > kot(data)) {
//				parent = cur;
//				cur = cur->_left;
//			}
//			else {
//				return false;
//			}
//		}
//
//		cur = new Node(data);
//		cur->_color = Colour::RED;
//		if (kot(parent->_data) < kot(data)) {
//			parent->_right = cur;
//		}
//		else {
//			parent->_left = cur;
//		}
//		cur->_parent = parent;
//
//		while (parent && parent->_color == RED) {
//			Node* grandfather = parent->_parent;
//			if (parent == grandfather->_left) {
//				Node* uncle = grandfather->_right;
//				// 叔叔存在且为红
//				if (uncle && uncle->_color == Colour::RED) {
//					parent->_color = uncle->_color = Colour::BLACK;
//					grandfather->_color = Colour::RED;
//
//					// 继续往上处理
//					cur = grandfather;
//					parent = cur->_parent;
//				}
//				else {
//					// 叔叔不存在 或者 存在且为黑
//					if (cur == parent->_left) {
//						RotateR(grandfather);
//						parent->_color = Colour::BLACK;
//						grandfather->_color = Colour::RED;
//					}
//					else {
//						RotateL(parent);
//						RotateR(grandfather);
//						grandfather->_color = Colour::RED;
//						cur->_color = Colour::BLACK;
//					}
//					break;
//				}
//			}
//			else {
//				Node* uncle == grandfather->_left;
//				// 叔叔存在且为红， 变色即可
//				if (uncle && uncle->_color == Colour::RED) {
//					parent->_color = uncle->_color = Colour::BLACK;
//					grandfather->_color = RED;
//
//					// 继续往上处理
//					cur = grandfather;
//					parent = cur->_parent;
//				}
//				else {
//					// 叔叔不存在， 或者存在且为黑
//					if (cur == parent->_right) {
//						RotateL(grandfather);
//						parent->_color = Colour::BLACK;
//						grandfather->_color = Colour::RED;
//					}
//					else {
//						RotateR(parent);
//						RotateL(grandfather);
//						cur->_color = Colour::BLACK;
//						grandfather->_color = Colour::RED;
//					}
//					break;	
//				}
//			}
//		}
//
//		_root->_col = BALCK;
//		
//	}
//
//private:
//	void RotateR(Node* parent)
//	{
//		Node* subL = parent->_left;
//		Node* subLR = subL->_right;
//
//		parent->_left = subLR;
//		subL->_right = parent;
//
//		if (subLR)
//			subLR->_parent = parent;
//
//		Node* parentParent = parent->_parent;
//		parent->_parent = subL;
//
//		//if (parentParent == nullptr)
//		if (parent == _root)
//		{
//			_root = subL;
//			subL->_parent = nullptr;
//		}
//		else
//		{
//			if (parentParent->_left == parent)
//			{
//				parentParent->_left = subL;
//			}
//			else
//			{
//				parentParent->_right = subL;
//			}
//
//			subL->_parent = parentParent;
//		}
//	}
//
//	void RotateL(Node* parent)
//	{
//		Node* subR = parent->_right;
//		Node* subRL = subR->_left;
//		parent->_right = subRL;
//		if (subRL)
//			subRL->_parent = parent;
//		Node* parentParent = parent->_parent;
//		subR->_left = parent;
//		parent->_parent = subR;
//		if (parentParent == nullptr)
//		{
//			_root = subR;
//			subR->_parent = nullptr;
//		}
//		else
//		{
//			if (parent == parentParent->_left)
//			{
//				parentParent->_left = subR;
//			}
//			else
//			{
//				parentParent->_right = subR;
//			}
//			subR->_parent = parentParent;
//		}
//	}
//
//private:
//	Node* _root;
//};




/***********************************写博客的第三份代码*****************************************************/
//#pragma once
//#include <iostream>
//#include <assert.h>
//using namespace std;
//
//// 枚举值表示颜色
//enum Colour
//{
//	RED,
//	BLACK
//};
//
//// 这里默认按 key/value 结构实现
//template <class K, class V>
//struct RBTreeNode {
//	// 这里更新控制平衡也要加入 parent指针
//	pair<K, V> _kv;
//	RBTreeNode<K, V>* _left;
//	RBTreeNode<K, V>* _right;
//	RBTreeNode<K, V>* _parent;
//	Colour _color;
//
//	RBTreeNode (const pair<K, V>& kv)
//		:_kv(kv)
//		,_left(nullptr)
//		,_right(nullptr)
//		,_parent(nullptr)
//		,_color(Colour::RED)
//	{ }
//};
//
//
//template<class K, class V>
//class RBTree {
//	typedef RBTreeNode<K, V> Node;
//public:
//	bool Insert(const pair<K, V>& kv) {
//		if (_root == nullptr) {
//			_root = new Node(kv);
//			_root->_color = BLACK;
//			return true;
//		}
//
//		Node* parent = nullptr;
//		Node* cur = _root;
//		while (cur) {
//			if (cur->_kv.first < kv.first) {
//				parent = cur;
//				cur = cur->_right;
//			}
//			else if (cur->_kv.first > kv.first) {
//				parent = cur;
//				cur = cur->_left;
//			}
//			else {
//				// 遇到相同键的值
//				return false;
//			}
//		}
//		// 退出while循环后，cur为空指针
//		cur = new Node(kv);
//		cur->_color = Colour::RED;
//		// 判断 cur 是在 parent 的左边还是右边
//		if (kv.first < parent->_kv.first) {
//			parent->_left = cur;
//			cur->_parent = parent;
//		}
//		else {
//			parent->_right = cur;
//			cur->_parent = parent;
//		}
//
//		// 目前新结点是染的红色，现在向上判断是否需要 对结点重新染色
//		// 如果 parent 结点为红色结点，则违反了规则4（不红红），需要进行修正操作
//		while (parent && parent->_color == Colour::RED) {
//			Node* grandfather = parent->_parent;
//			Node* uncle = nullptr;
//			// 根据 parent 结点的位置，来给 uncle 结点赋值
//			if (parent == grandfather->_left) {
//				uncle = grandfather->_right;
//			}
//			else {
//				uncle = grandfather->_left;
//			}
//			// uncle 的三种情况，uncle 结点不存在，
//			// uncle 结点存在，uncle 结点可能是红色，也可能是黑色
//			// uncle 结点可能为空结点
//			if (uncle != nullptr && uncle->_color == Colour::RED) {
//				grandfather->_color = Colour::RED;
//				uncle->_color = parent->_color = Colour::BLACK;
//				// 继续向上传递
//				cur = grandfather;
//				parent = cur->_parent;
//			}
//			else if ((uncle == nullptr) || (uncle != nullptr && uncle->_color == Colour::BLACK)) {
//				// uncle 结点是空结点 或者 uncle 结点的颜色为 黑色
//				// 采用 旋转+调色，根据情况采用四种旋转方式后
//				// 对 grandfather、parent 结点调色
//				// LL
//				if (grandfather->_left == parent && parent->_left == cur) {
//					RotateR(grandfather);
//					parent->_color = Colour::BLACK;
//					grandfather->_color = Colour::RED;
//				}
//				// LR
//				else if (grandfather->_left == parent && parent->_right == cur) {
//					RotateLR(grandfather);
//					cur->_color = Colour::BLACK;
//					grandfather->_color = Colour::RED;
//				}
//				// RR
//				else if (grandfather->_right == parent && parent->_right == cur) {
//					RotateL(grandfather);
//					parent->_color = Colour::BLACK;
//					grandfather->_color = Colour::RED;
//				}
//				// RL
//				else if (grandfather->_right == parent && parent->_left == cur) {
//					RotateRL(grandfather);
//					cur->_color = Colour::BLACK;
//					grandfather->_color = Colour::RED;
//				}
//				else {
//					// 出现异常情况，不符合四种旋转情况
//					assert(false);
//				}
//			}
//			else {
//				// 发生了异常情况，uncle结点存在且 颜色 非黑非红
//				assert(false);
//			}
//		}
//
//		// 默认 根结点为 黑色
//		_root->_color = Colour::BLACK;
//		return true;
//	}
//
//	bool Find(const K& key) {
//		Node* cur = _root;
//		while (cur) {
//			if (cur->_kv.first < key) {
//				cur = cur->_right;
//			}
//			else if (cur->_kv.first > key) {
//				cur = cur->_left;
//			}
//			else {
//				return true;
//			}
//		}
//		return false;
//	}
//
//	void InOrder() {
//		_InOrder(_root);
//		cout << endl;
//	}
//
//	bool Check(Node* root, int blackNum, const int refNum) {
//		if (root == nullptr) {
//			// 前序遍历走到空时，意味着一条路径走完了
//			// cout << blackNum << endl;
//			// 规则5（黑路同）
//			if (refNum != blackNum) {
//				cout << "存在黑色结点的数量不相等的路径" << endl;
//				return false;
//			}
//			return true;
//		}
//
//		// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了
//		// 规则4（不红红）
//		if (root->_color == Colour::RED && root->_parent && root->_parent->_color == Colour::RED) {
//			// 违反了 不红红规则
//			cout << root->_kv.first << "存在连续的红色结点" << endl;
//			return false;
//		}
//
//		if (root->_color == Colour::BLACK) {
//			blackNum++;
//		}
//
//		return Check(root->_left, blackNum, refNum)
//			&& Check(root->_right, blackNum, refNum);
//	}
//
//	bool IsBalanceTree() {
//		// 空树不是一棵红黑树，连根结点都没有，不能保证根结点为黑色结点
//		if (_root == nullptr) {
//			cout << "根结点为空，这是一棵空树" << endl;
//			return false;
//		}
//
//		// 根结点一定要是黑色结点
//		if (_root->_color == Colour::RED) {
//			cout << "根结点为红色" << endl;
//			return false;
//		}
//
//		// 参考值 通过遍历左孩子指针直到空来得到这条路径拥有的黑色结点数量
//		int refNum = 0;
//		Node* cur = _root;
//		while (cur) {
//			if (cur->_color == Colour::BLACK) {
//				++refNum;
//			}
//			cur = cur->_left;
//		}
//
//		return Check(_root, 0, refNum);
//	}
//private:
//	void RotateL(Node* cur) {	// 左单旋
//		Node* parent = cur->_parent;
//		Node* subR = cur->_right;
//		Node* subRL = subR->_left;
//
//		// 先操作 subR 和 subRL 之间的链接
//		// 左单旋的目的，是让 subR 替代 cur 作为子树的根结点
//		subR->_left = cur;
//		cur->_parent = subR;
//		cur->_right = subRL;	// sub 的左子树归 cur 的右孩子指针管
//
//		// subRL 可以为空， 就是高度 h 为 0 的时候
//		// 所以需要特判
//		if (subRL != nullptr)
//			subRL->_parent = cur;
//
//		// 注意 cur 的父结点 parent 还链接着 cur，需要断开链接，让 parent的其中一个孩子指针指向 subR
//		// 同时 parent 作为 cur 的父结点，当 cur 为根结点时，parent 为空，也需要特判
//		if (parent == nullptr) {
//			// 说明 cur 是根结点
//			_root = subR;
//			subR->_parent = nullptr;
//		}
//		else {
//			// 说明 cur 不是根节点
//			if (cur == parent->_left) {
//				parent->_left = subR;
//			}
//			else {
//				parent->_right = subR;
//			}
//			subR->_parent = parent;
//		}
//	}
//
//	void RotateR(Node* cur) {	// 右单旋
//		Node* parent = cur->_parent;// cur的父结点
//		Node* subL = cur->_left;	// cur的左孩子
//		Node* subLR = subL->_right;	// subL的右孩子
//
//		// cur 成为 subL 的右孩子
//		subL->_right = cur;
//		cur->_parent = subL;
//
//		// subLR 成为 cur 的左孩子
//		cur->_left = subLR;
//		if (subLR != nullptr)
//			subLR->_parent = cur;
//
//		if (parent == nullptr) {
//			// 说明 cur 是根结点，parent 才为空结点
//			_root = subL;
//			subL->_parent = nullptr;
//		}
//		else {
//			// parent 是非空结点， 但是不知道 cur 是 parent 的哪个孩子
//			if (cur == parent->_left) {
//				parent->_left = subL;
//			}
//			else {
//				parent->_right = subL;
//			}
//			subL->_parent = parent;
//		}
//	}
//
//	void RotateLR(Node* cur) {	// 左右双旋
//		Node* subL = cur->_left;
//		Node* subLR = subL->_right;
//
//		RotateL(subL);
//		RotateR(cur);
//
//	}
//
//	void RotateRL(Node* cur) {
//		Node* subR = cur->_right;
//		Node* subRL = subR->_left;
//
//		RotateR(subR);
//		RotateL(cur);
//
//	}
//
//	void _InOrder(Node* root) {
//		if (root == nullptr) {
//			return;
//		}
//
//		_InOrder(root->_left);
//		cout << root->_kv.first << " ";
//		_InOrder(root->_right);
//	}
//private:
//	Node* _root = nullptr;
//};


// 说明：
// 1. 在完善迭代器前，请先确保红黑树实现成功
// 2. 迭代器实现好后，与红黑树结合起来，能够通过红黑树的迭代器遍历红黑树
// 3. 此处给的迭代器实现并不完整，缺少--操作，大家只需要将++实现即可，此处主要了解红黑树迭代器原理即可
//    要实现完整的迭代器需要对红黑树进行改造，有兴趣可参考侯捷《STL源码剖析》

// 枚举值表示颜色
enum Colour
{
	RED,
	BLACK
};

// 这里默认按 key/value 结构实现
template <class T>
struct RBTreeNode {
	// 这里更新控制平衡也要加入 parent指针
	T _data;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Colour _color;

	RBTreeNode (const T& data)
		:_data(data)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_color(Colour::RED)
	{ }
};


//﻿template <class T>
template <class T>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T> Self;

	Node* _node;

	RBTreeIterator(Node* node)
		:_node(node)
	{ }

	// 请完善迭代器的++操作，让迭代器可以移动
	Self& operator++() {
		if (_node == nullptr) {
			// 如果当前已经是 end()，++操作是未定义的，通常保持为 end()
			return *this;
		}
		if (_node->_right) {
			Node* cur = _node->_right;
			while (cur->_left != nullptr) {
				cur = cur->_left;
			}
			// while循环结束后，cur为右子树的最左结点
			_node = cur;
			return *this;
		}
		else {
			// 左右子树都遍历完毕， 往回走
			if (_node->_parent != nullptr) {
				while (_node->_parent != nullptr && _node == _node->_parent->_right) {
					_node = _node->_parent;
				}
				_node = _node->_parent;
			}
			else {
				// 说明 _node 现在是根结点，且已经遍历完成，可以返回空指针
				_node = nullptr;
			}
			return *this;
		}
	}

	// 请完善下面两个操作，让迭代器可以像指针一样操作
	T& operator*() {
		return _node->_data;
	}
	T* operator->() {
		return &_node->_data;
	}

	// 请完善下面两个操作，让迭代器能够支持比较
	bool operator!=(const Self& s)const {
		return _node != s._node;
	}
	bool operator==(const Self& s)const {
		return _node == s._node;
	}
};



// 注意：红黑树完整操作参考课堂代码
// 此处给红黑树添加迭代器，其他用不到的操作暂被拿掉，只留下红黑树构建的核心操作
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T> Iterator;
	typedef RBTreeIterator<const T> const_Iterator;
public:
	// 请给红黑树的迭代器取别名，方便后序使用
	// ________________________

	// 请完善Begin() 和 End()方法
	Iterator begin() {
		Node* cur = _root;
		while (cur && cur->_left) {
			cur = cur->_left;
		}
		return Iterator(cur);
	}

	Iterator end() {
		return Iterator(nullptr);
	}

	//const_Iterator cbegin() const{
	//	Node* cur = _root;
	//	while (cur && cur->_left) {
	//		cur = cur->_left;
	//	}
	//	return const_Iterator(cur);
	//}

	//const_Iterator cend() const {
	//	return const_Iterator(nullptr);
	//}


	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}


	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_color = BLACK;
			return true;
		}


		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}


		cur = new Node(data);
		// 新增节点。颜色红色给红色
		cur->_color = RED;
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_color == RED)
		{
			Node* grandfather = parent->_parent;
			//    g
			//  p   u
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_color == RED)
				{
					// u存在且为红 -》变色再继续往上处理
					parent->_color = uncle->_color = BLACK;
					grandfather->_color = RED;


					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					// u存在且为黑或不存在 -》旋转+变色
					if (cur == parent->_left)
					{
						//    g
						//  p   u
						//c
						//单旋
						RotateR(grandfather);
						parent->_color = BLACK;
						grandfather->_color = RED;
					}
					else
					{
						//    g
						//  p   u
						//    c
						//双旋
						RotateL(parent);
						RotateR(grandfather);


						cur->_color = BLACK;
						grandfather->_color = RED;
					}
					break;
				}
			}
			else
			{
				//    g
				//  u   p
				Node* uncle = grandfather->_left;
				// 叔叔存在且为红，-》变色即可
				if (uncle && uncle->_color == RED)
				{
					parent->_color = uncle->_color = BLACK;
					grandfather->_color = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 叔叔不存在，或者存在且为黑
				{
					// 情况二：叔叔不存在或者存在且为黑
					// 旋转+变色
					//      g
					//   u     p
					//            c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_color = BLACK;
						grandfather->_color = RED;
					}
					else
					{
						//		g
						//   u     p
						//      c
						RotateR(parent);
						RotateL(grandfather);
						cur->_color = BLACK;
						grandfather->_color = RED;
					}
					break;
				}
			}
		}

		_root->_color = BLACK;
		return true;
	}

private:

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* parentParent = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;


		if (parentParent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}
	}


	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parentParent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}
	}

	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

private:
	Node* _root = nullptr;
};